package oct2013;

/**
 * @author Yinzi Chen
 * @date Nov 14, 2013
 */
public class ScrambleString {
    public boolean isScramble(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n != m)
            return false;
        boolean[][][] dp = new boolean[n][n][n + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i + k > n || j + k > n)
                        break;
                    for (int p = 1; p < k; ++p) {
                        if (dp[i][j + k - p][p] && dp[i + p][j][k - p]
                                || dp[i][j][p] && dp[i + p][j + p][k - p]) {
                            dp[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }

}
